package com.suanfa.dp;

import java.util.Stack;

/*
 * 最长有效括号 给定字符串中，有效关闭的最长括号 动态规划版
 * https://leetcode.cn/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
 *
 * 状态转移方程  当s[i] = ")" s[i-1]='('  dp[i] = dp[i-2] + 2
 *
 *
 */
    public class StackDpTest {
    public static void main(String[] args) {
        String ss = "(()";
        System.out.println(getLarge(ss));
    }

    public static int getLarge(String s){
        Stack<Integer> stackTest = new Stack();
        stackTest.push(-1);
        int masxLength = 0;
        char[] strs = s.toCharArray();
        for(int  i =0; i< strs.length; i++){
            if(strs[i] == '('){
                stackTest.push(i);
            }else {
                stackTest.pop();
                //防止开始两个））出现异常
                if(stackTest.isEmpty()){
                    stackTest.push(i);
                }else {
                    masxLength = Math.max(i - stackTest.peek(), masxLength);
                }
            }
        }
        return masxLength;
    }

}
